<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        class HashTable {
            constructor () {
                this.storage = []
                this.limit = 7
                this.count = 0
                function hashFunc (str, size) {
                    var hashCode = 0
                    for (let i = 0; i < str.length; i++) {
                        hashCode = 37 * hashCode + str.charCodeAt(i);
                    }
                    var index = hashCode % size
                    return index
                }
            }
            put (key, value) {
                let index = this.hashFunc(key, this.limit)
                let bucket = this.storage[index]
                if (bucket === null) {
                    bucket = []
                    this.storage[index] = bucket
                }
                for (let i = 0; i < bucket.length; i++) {
                    const tuple = bucket[i];
                    if (tuple[0] == key) {
                        tuple[1] = value
                        return
                    }
                }
                bucket.push([key, value])
                this.count += 1
                if (this.count > this.limit * 0.75) {
                    let newSize = this.getPrime(limit * 2)
                    this.resize(newSize)
                }   
            }
            get(key) {
                let index = this.hashFunc(str, this.limit)
                let bucket = this.storage[index]
                for (let i = 0; i < bucket.length; i++) {
                    let tuple = bucket[i];
                    if (tuple[0] == key) {
                        return tuple[1]
                    }
                }
                return null
            }
            remove(key) {
                let index = this.hashFunc(str, this.limit)
                let bucket = this.storage[index]
                for (let i = 0; i < bucket.length; i++) {
                    const tuple = bucket[i];
                    if (tuple[0] == key) {
                        bucket.splice(i, 1)
                        this.count -= 1
                        if (this.limit > 7 && this.count < this.limit * 0.25) {
                            let newSize = this.getPrime(Math.floor(this.limit / 2))
                            this.resize(newSize)
                        }
                        return bucket[1]
                    }
                }
                return null
            }
            size() {
                return this.count
            }
            isEmpty() {
                return this.count == 0
            }
            resize(newLimit) {
                let oldStorage = this.storage
                this.storage = []
                this.count = 0
                this.limit = newLimit
                for (let i = 0; i < oldStorage.length; i++) {
                    const bucket = oldStorage[i];
                    if (bucket == null) continue
                    for (let j = 0; j < bucket.length; j++) {
                        const tuple = bucket[j];
                        this.put(tuple[0], tuple[1])
                    }
                }
            }
            isPrime(num) {
                // 取平方根
                let temp = parseInt(Math.sqrt(num))
                for (let i = 2; i <= temp; i++) {
                    if (temp % i == 0) {
                        return false
                    }
                }
                return true
            }
            getPrime(num) {
                while(!this.isPrime(num)) {
                    num++
                }
                return num
            }
        }
    </script>
</body>
</html>